/*
 * @lc app=leetcode.cn id=1477 lang=cpp
 *
 * [1477] 找两个和为目标值且不重叠的子数组
 */

// @lc code=start
class Solution
{
public:
    typedef pair<int, int> pii;
    int minSumOfLengths(vector<int> &arr, int target)
    {
        vector<pii> ranges;
        int n = arr.size(), l = 0, sum = 0;
        for (int r = 0; r < n; r++)
        {
            sum += arr[r];
            while (sum > target && l <= r)
            {
                sum -= arr[l++];
            }
            if (sum == target)
            {
                ranges.push_back(pii(l, r));
            }
        }

        int ans = -1, preIdx = -1, preMin = n + 1;
        for (auto range : ranges)
        {
            while (ranges[preIdx + 1].second < range.first)
            {
                preIdx++;
                preMin = min(preMin, ranges[preIdx].second - ranges[preIdx].first + 1);
            }
            if (preIdx == -1)
                continue;
            if (ans == -1 || ans > preMin + range.second - range.first + 1)
            {
                ans = preMin + range.second - range.first + 1;
            }
        }

        return ans;
    }
};
// @lc code=end
